package net.tp.struct.adt;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 *
 * <p>Skip List.</p>
 *
 * <p>Skip List is a bunch of linked lists connected together to search quickly an item. This is analogous to regular and express subway lines: regular subway line stops at every stops while express subway line skip a few stops so that passengers can quickly reach a destination.</p>
 *
 * <p>Implementing Skip List using many linked lists literally can be very cumbersome. It's easier to implement the skip list using one linked list and each node has many links. To bottom  level link always links to the next node while the higher level link can skip nodes.</p>
 *
 * <p>Ideally, a balanced skip list should look like this (the first node is a sentinel node with no information):</p>
 * <pre>
 *  ⊗───────────── 4
 *  ⊗───── 2 ───── 4 ───── 6
 *  ⊗─ 1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 6 ─ 7
 * </pre>
 *
 * <p>In this ideal situation, each level link skips one node from the lower level, and there are total $log(n)$ levels to support list of n elements. However, it's expensive to maintain such balance if we support both inserts and deletes. To make the implementation practical, the skip list uses randomization. When a node is inserted at the lowest level (level 0), there is a 1/2 chance that it will be linked in the next level (level 1) and 1/4 chance for level 2, etc. A new node always appear in the lowest level. To decide how many additional levels a new node has, we can keep tossing the coin until it turns tail, the number of heads is the number of additional levels. To simplify the implementation, I use this formula: {@code 1 + Integer.numberOfTrailingZeros(random.nextInt())}. The method {@code random.nextInt()} gives all possible combination of 32 bits. Each bit in the generated pseudorandom has 50% chance of being 0. So the maximum number of levels that this skip list supports is 33. So it supports around $2^32$ elements.
 * </p>
 *
 * <pre>
 *
 *  ⊗─ 4
 *
 *  ⊗─ 2 ─ 4
 *
 *  ⊗───── 3
 *  ⊗─ 2 ─ 3 ─ 4
 *
 *  ⊗───────── 3
 *  ⊗─ 1 ─ 2 ─ 3 ─ 4
 *
 *  ⊗───────────────── 7
 *  ⊗───────── 3 ───── 7
 *  ⊗─ 1 ─ 2 ─ 3 ─ 4 ─ 7
 *
 *  ⊗───────────────────── 7
 *  ⊗───────── 3 ───── 5 ─ 7
 *  ⊗─ 1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 7
 *
 *  ⊗───────────────────────── 7
 *  ⊗───────── 3 ───── 5 ───── 7
 *  ⊗─ 1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 6 ─ 7
 *
 *  ⊗───────────────────── 7
 *  ⊗───────────── 5 ───── 7
 *  ⊗─ 1 ─ 2 ─ 4 ─ 5 ─ 6 ─ 7
 *
 *  ⊗───────────────── 7
 *  ⊗───────────────── 7
 *  ⊗─ 1 ─ 2 ─ 4 ─ 6 ─ 7
 * </pre>
 *
 * @author Trung Phan
 *
 * @time $O(\log n)$ with very high probability for insert, delete and search.
 *
 */
public class SkipList<E> {

    /**
     * 33 because the formula 1 + Integer.numberOfTrailingZeros(random.nextInt()) gives max 33.
     */
    private static final int MAX_LEVELS = 33;

    private final Comparator<? super E> comparator;

    /**
     * head is a sentinel node. It does not store the real key/value.
     */
    private SkipNode<E> head = new SkipNode<>(null, MAX_LEVELS);

    private Random random = new Random();

    private int size;

    public SkipList(Comparator<? super E> comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public void add(E element) {
        SkipNode<E> n = find(element);
        if (n != null) {
            return;
        }

        int levels = 1 + Integer.numberOfTrailingZeros(random.nextInt());

        SkipNode<E> newNode = new SkipNode<>(element, levels);
        n = head;
        for (int level = levels-1; level >= 0; level--) {
            while (n.next[level] != null && comparator.compare(element, n.next[level].element) > 0)
                n = n.next[level];

            newNode.next[level] = n.next[level];
            n.next[level] = newNode;
        }

        size++;
    }

    public boolean contains(E element) {
        SkipNode<E> n = find(element);
        return n != null;
    }

    public boolean remove(E element) {
        boolean found = false;

        SkipNode<E> n = head;
        for (int level = MAX_LEVELS-1; level >= 0; level--) {
            while (n.next[level] != null) {
                int cmp = comparator.compare(element, n.next[level].element);
                if (cmp == 0) {
                    found = true;
                    n.next[level] = n.next[level].next[level];
                    break;
                }
                else if (cmp < 0) {
                    break;
                }
                n = n.next[level];
            }
        }

        if (found) size--;

        return found;
    }

    private SkipNode<E> find(E element) {
        SkipNode<E> n = head;
        for (int level = MAX_LEVELS - 1; level >= 0; level--) {
            int cmp;
            for (; n.next[level] != null && (cmp = comparator.compare(element, n.next[level].element)) >= 0; n = n.next[level]) {
                if (cmp == 0) return n.next[level];
            }
        }
        return null;
    }


    @Override
    public String toString() {
        int levels = 0;
        while (head.next[levels] != null) levels++;

        StringBuilder[] builders = new StringBuilder[levels];
        for (int i = 0; i < levels; i++) builders[i] = new StringBuilder("⊗");
        SkipNode<E>[] next = Arrays.copyOf(head.next, levels);

        for (SkipNode<E> n = head.next[0]; n != null; n = n.next[0]) {
            String label = n.element.toString();
            for (int level = 0; level < levels && next[level] != null; level++) {
                builders[level].append("─");
                if (next[level] == n) {
                    builders[level].append(" ").append(label).append(" ");
                    next[level] = next[level].next[level];
                }
                else {
                    for (int i = -2; i < label.length(); i++) builders[level].append("─");
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for (int level = levels - 1; level >= 0; level--) {
            result.append(builders[level]);
            if (level > 0) result.append('\n');
        }

        return result.toString();
    }

    public static void main(String ... args) {
        SkipList<Integer> skipList = new SkipList<>(Comparator.naturalOrder());

        skipList.add(4); System.out.println(skipList);
        System.out.println();
        skipList.add(2); System.out.println(skipList);
        System.out.println();
        skipList.add(3); System.out.println(skipList);
        System.out.println();
        skipList.add(1); System.out.println(skipList);
        System.out.println();
        skipList.add(7); System.out.println(skipList);
        System.out.println();
        skipList.add(5); System.out.println(skipList);
        System.out.println();
        skipList.add(6); System.out.println(skipList);
        System.out.println();

        skipList.remove(3); System.out.println(skipList);
        System.out.println();
        skipList.remove(5); System.out.println(skipList);
        System.out.println();

    }

    public static class SkipNode<E> {

        private E element;

        private SkipNode<E>[] next;

        @SuppressWarnings({"unchecked", "rawtypes"})
        public SkipNode(E element, int level) {
            this.element = element;
            this.next = new SkipNode[level];
        }
    }

}
